/* ----------------------------------------------------------------------------------------------------------------
 * QuadTree
 * ----------------------------------------------------------------------------------------------------------------
 */
package pure.engine.world 
{
	import flash.geom.Rectangle;
	import pure.engine.entity.IEntity;
	
	/**
	 * 四叉树
	 * @author Pure
	 * 
	 */
public class QuadTree 
{
	public function QuadTree(x:Number, y:Number, width:Number, height:Number, root:Boolean = false)
	{
		if (!root)
		{
			
		}
		else
		{
			_splinterMinimum = (width + height) / (2 * _divisions);
		}
		
		_entities = { };
		
		_canSplinter = (width > _splinterMinimum) || (height > _splinterMinimum);
		
		_leftEdge = x;
		_rightEdge = x + width;
		_topEdge = y;
		_bottomEdge = y+height;
		_halfWidth = width / 2;
		_midX = _leftEdge+_halfWidth;
		_halfHeight = height/2;
		_midY = _topEdge+_halfHeight;
	}
	
	
	
	protected static var _divisions:uint = 6;
	protected static var _splinterMinimum:int;
	
		
	protected var _quadRect:Rectangle;
	protected var _entities:Object;
	
	protected var _northWestTree:QuadTree, _northEastTree:QuadTree,   // 西北 ，东北
				  _southWestTree:QuadTree, _southEastTree:QuadTree;   // 西南 ，东南
	
	protected var _leftEdge:Number, _rightEdge:Number, _topEdge:Number, _bottomEdge:Number,
				  _halfWidth:Number, _halfHeight:Number, _midX:Number, _midY:Number;

	protected var _canSplinter:Boolean;
	
	
	
	/**
	 * 毁灭
	 */
	public function destroy():void
	{
		this._entities  = [];
		_northWestTree = _northEastTree = _southEastTree = _southWestTree = null;
	}
		
	/**
	 * 加入
	 * 
	 * @param entity
	 */
	public function add(entity:IEntity):void 
	{
		var rect:Rectangle = entity.worldRect;
		
		// 无法再分裂or对象完全覆盖该Quad
		if (!_canSplinter || ( rect.left <= _leftEdge && 
							   rect.top <= _topEdge &&
							   rect.right >= _rightEdge && 
							   rect.bottom >= _bottomEdge)) 
		
		{
			_entities[entity.id] = entity;
			return;
		}

		// 完全西半区
		if((rect.left > _leftEdge) && (rect.right < _midX))
		{
			// 完全北半区
			if((rect.top > _topEdge) && (rect.bottom < _midY))
			{
				if (_northWestTree == null)
				{
					_northWestTree = new QuadTree(_leftEdge,_topEdge,_halfWidth,_halfHeight);
				}
				
				_northWestTree.add(entity);
				return;
			}
			
			// 完全南半区
			if((rect.top > _midY) && (rect.bottom < _bottomEdge))
			{
				if (_southWestTree == null)
				{
					_southWestTree = new QuadTree(_leftEdge,_midY,_halfWidth,_halfHeight);
				}
				
				_southWestTree.add(entity);
				return;
			}
		}
		// 完全东半区
		if((rect.left > _midX) && (rect.right < _rightEdge))
		{
			// 完全北半区
			if((rect.top > _topEdge) && (rect.bottom < _midY))
			{
				if (_northEastTree == null)
				{
					_northEastTree = new QuadTree(_midX,_topEdge,_halfWidth,_halfHeight);
				}
				
				_northEastTree.add(entity);
				return;
			}
			
			// 完全南半区
			if((rect.top > _midY) && (rect.bottom < _bottomEdge))
			{
				if (_southEastTree == null) 
				{
					_southEastTree = new QuadTree(_midX,_midY,_halfWidth,_halfHeight);
				}
				
				_southEastTree.add(entity);
				return;
			}
		}
			
		
		// 不完全包含，计算局部区域
		if ((rect.bottom > _topEdge) && (rect.top < _midY))
		{
			// 部分覆盖西北区域
			if((rect.right > _leftEdge) && (rect.left < _midX))
			{
				if (_northWestTree == null) 
				{
					_northWestTree = new QuadTree(_leftEdge,_topEdge,_halfWidth,_halfHeight);
				}
				
				_northWestTree.add(entity);
			}
			
			// 部分覆盖东北区域
			if((rect.right > _midX) && (rect.left < _rightEdge))
			{
				if (_northEastTree == null) 
				{
					_northEastTree = new QuadTree(_midX,_topEdge,_halfWidth,_halfHeight);
				}
				
				_northEastTree.add(entity);
			}
		}

		if ((rect.bottom > _midY) && (rect.top < _bottomEdge))
		{
			// 部分覆盖东南区域
			if((rect.right > _midX) && (rect.left < _rightEdge))
			{
				if (_southEastTree == null) 
				{
					_southEastTree = new QuadTree(_midX,_midY,_halfWidth,_halfHeight);
				}
				
				_southEastTree.add(entity);
			}
			
			// 部分覆盖西南区域
			if((rect.right > _leftEdge) && (rect.left < _midX))
			{
				if (_southWestTree == null)
				{
					_southWestTree = new QuadTree(_leftEdge,_midY,_halfWidth,_halfHeight);
				}
				
				_southWestTree.add(entity);
			}
		}
	}

	

	/**
	 * 检索
	 * @param rect
	 */
	/*public function retrieve(rect:Rectangle):Array {
		var list:Array = [];
		if(!this.topLeft) {
			list.push.apply(list, this._entityList);
			return list;
		}
			
		// 如果所取区块比本身区域还大，那么它所有子树的children都取出
		if( rect.x <= _quadRect.x && rect.y<= _quadRect.y && rect.x+rect.width>=_quadRect.right && rect.y+rect.height >= _quadRect.bottom) {
		   list.push.apply(list,this._entityList)
		   list.push.apply(list,this.topLeft.retrieve(rect))
		   list.push.apply(list,this.topRight.retrieve(rect))
		   list.push.apply(list,this.bottomLeft.retrieve(rect))
		   list.push.apply(list,this.bottomRight.retrieve(rect))
		   return list;
		} 
		
		// 否则就只取对应的区域子树
		var rectRight:Number = rect.x+rect.width
		var rectBottom:Number = rect.y+rect.height
	  
		// 完全在1/4分区里 
		if((rect.x>_quadRect.x) && (rectRight< this._midX)) {				
			if( rect.y > _quadRect.y && rectBottom <this._midY) {
				list.push.apply(list,this.topLeft.retrieve(rect))
				return list;
			}
			if(rect.y >this._midY && rectBottom < this._quadRect.bottom) {
				list.push.apply(list,this.bottomLeft.retrieve(rect))
				return list;
			}
		}
		if (rect.x > _midX && rectRight < _quadRect.right) {
			if (rect.y > _quadRect.y && rectBottom < _midY) {
				list.push.apply(list,this.topRight.retrieve(rect))
				return list
			}
			if (rect.y > _midY && rectBottom < _quadRect.bottom) {
				list.push.apply(list,this.bottomRight.retrieve(rect))
				return list
			}
		}
			
		// 只要有部分在分区里，也放到对应分区里，但注意可以重复放			
		
		// 部分一定在上边
		if (rectBottom > _quadRect.y && rect.y < _midY) {
			if(rect.x < _midX && rectRight > _quadRect.x ) {
				list.push.apply(list,this.topLeft.retrieve(rect));
			}
			if( rect.x < _quadRect.right && rectRight > _midX ) {
				list.push.apply(list,this.topRight.retrieve(rect));
			}
		}
		// 部分一定在下边
		if(rectBottom > _midY && rect.y < _quadRect.bottom) {
			if(rect.x < _midX && rectRight >_quadRect.x) {
				list.push.apply(list,this.bottomLeft.retrieve(rect));
			}
			if(rect.x < _quadRect.right && rectRight >_midX) {
				list.push.apply(list,this.bottomRight.retrieve(rect));
			}
		}
		return list;	
	}*/

}

}